1. Field of the Invention
This invention generally relates to the field of data communication networks. More particularly, the present invention relates to a novel system and method for ensuring bandwidth to different classes of traffic, limiting the classes of traffic to corresponding maximum bandwidths, and dynamically allocating bandwidth to classes needing more than their maximum bandwidth when there exists available bandwidth.
2. Description of Related Art
Most commercial communication networks incorporate network switching devices, such as computer switches or routers, for example, to aggregate streams of data onto a network link and funnel the data traffic to its destination. These switching devices typically employ queuing methodologies to manage the flow of data streams onto the network link. For very high-speed network links, it is important that queuing methodologies be computationally simple so that the switch or router does not become a bottleneck. One such methodology is the Deficit Round Robin (DRR) technique (M. Shreedhar and G. Varghese, Efficient Fair Queuing Using Deficit Round Robin, Washington University, St. Louis, Mo. (Oct. 16, 1995)). DRR was designed to ensure that each class of traffic being transmitted out of a particular network device output port receives a user-selectable percentage of the port""s bandwidth.
FIG. 1 illustrates a representative system 100, employing DRR. As indicated in FIG. 1, a plurality of input streams of packetized data, representing different classes of traffic, flow into the output port 105 of a network switching device. These streams are captured by queues 110A-110M. As packets enter queues 110A-110M, their lengths are stored in a manner that enables the queue servicing algorithm to quickly obtain the length of the packet from the head packet of each queue. The user assigns each of the queues 110A-110M a xe2x80x9cquantumxe2x80x9d number of bytes, based on the class of traffic of each queue. The ratio of each of the queue""s 110A-110M quantum to the total of all quanta represents the fraction of port bandwidth that each queue should receive. For example, queue 110A may represent a lower class of traffic and may be allocated a quantum of 500 bytes while queue 110B may represent a higher class and may be allocated a quantum of 1000 bytes. Queue 110C may represent an even higher class of traffic and may be allocated a quantum of 2000 bytes. If the total of all quanta is 10,000 bytes, then queue 110A should receive at least 500/10,000, or 5% of the output bandwidth. Likewise, queue 110B should receive 10% and 110C 20% of the bandwidth.
DRR incorporates xe2x80x9cdeficit countersxe2x80x9d 120A-120M, which track how many bytes a queue may send. During an initialization stage, deficit counters 120A-120M are initialized to zero. During operation, DRR examines each of the queues 110A-110M in a round-robin fashion (i.e., returning to the first queue 110A after the final queue 110M has been observed). If there are no packets in the queue being examined, then that queue is skipped and the next queue is examined. If a queue, for example queue 110C, has at least one packet to send, then the quantum corresponding to queue 110C is added to its deficit counter 120C. DRR then compares the length of the head packet of queue 110C, with the number of bytes in deficit counter 120C. If the length is less than or equal to deficit counter 120C, the packet is dequeued and transmitted while deficit counter 120C is decremented by the byte length of the packet. DRR then examines queue 110C again to determined whether there exists another packet in queue 110C, whose length is less than the number of bytes contained in deficit counter 120C. If so, the packet is dequeued, transmitted, and deficit counter 120C decremented.
This process is repeated until there are either no packets in queue 110C or the length of the packet at the head of queue 110C is greater than the number of bytes contained in deficit counter 120C. If there are no packets in queue 110C, deficit counter 120C is set to zero and the next queue is examined.
It is to be noted, however, that there are situations in which one queue may need more than its allocated target bandwidth while other queues are dormant. There are other situations where it may be desirable to ensure a predetermined bandwidth to a queue while enabling it to operate at a higher bandwidth if there exists available bandwidth.
What is needed, therefore, is a method and system that ensures bandwidth to different classes of traffic, limits the classes of traffic to a maximum bandwidth, and enables pre-selected classes to use more than their maximum bandwidth when there is bandwidth available.